﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;

namespace DataStructure.Interview
{
    public class Question01
    {
        public static bool IsUniquChar3(string str)
        {
            // if the str allow to destroy, we could sorting the str in O(nlogn) and liner check.

            return false;
        }

        /// <summary>
        /// if str is only a-z
        /// </summary>
        /// <param name="str"></param>
        /// <returns></returns>
        public static bool IsUniquChar2(string str)
        {
            if (string.IsNullOrEmpty(str))
                return false;

            int checker = 0; // as only a-z, then only 26 bit need to store and to check
            foreach (char item in str)
            {
                int diff = item - 'a';
                if ((checker & (1 << diff)) > 0)
                {
                    return false;
                }
                checker |= (1 << diff);
            }

            return true;
        }

        public static bool IsUniquChar(string str)
        {
            if (string.IsNullOrEmpty(str))
                return false;

            BitArray haschar = new BitArray(26);
            foreach (var c in str)
            {
                int i = (int)c - (int)'a';
                if (haschar[i])
                    return false;
                else
                    haschar[i] = true;
            }
            return true;
        }

    }
}
